A Referendum Puzzle
Here is another puzzle from Konstantin Knop.
Puzzle. A town has 801 residents, and they vote on 9 different questions. On each question, everyone votes either “Yes” or “No”, and the majority wins. A resident is happy with the result of a question if the final decision matches their own vote. We will call a resident satisfied if they are happy with at least 5 of the 9 final decisions. What is the smallest possible number of satisfied residents?
I leave the solution to the reader, but I want to recast the puzzle in the language of coding theory.
Write each ballot as a string of 9 zeros and ones. For example, a 1 can mean “Yes” and a 0 can mean “No”. A ballot is then a point in the 9-dimensional Hamming cube. The final result is another string of 9 zeros and ones, obtained by taking the majority vote in each coordinate.
The Hamming distance between two strings is the number of positions in which they differ. A resident is satisfied exactly when their ballot has Hamming distance at most 4 from the final result. So the puzzle becomes:
Puzzle. Given 801 binary strings of length 9, how few can lie within Hamming distance 4 of their coordinate-by-coordinate majority?
I promised not to give away the solution, but I can’t resist one more observation: we can flip zeros and ones in any coordinate without changing the problem. Therefore, without loss of generality, we may assume that the final result is 111111111. Then we can restate the puzzle again.
Puzzle. Given 801 binary strings of length 9 such that every coordinate contains at least 401 ones, how few of the strings can have at least five ones?
Share:
Leave a comment